package com.demo.java.OD101_150.OD132;

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【计算礼品发放的最小分组数目】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/145725730
 */
public class OdMain {
    public static void main(String[] args) {
        try {
            // 获取用户输入
            Scanner scan = new Scanner(System.in);
            String input = scan.nextLine(); // 获取最大值 maxValue
            int maxValue = Integer.parseInt(input); // 将输入转为整数

            // 如果 maxValue 为负数，输出错误信息并退出
            if (maxValue < 0) {
                System.out.println("input error");
                return;
            }

            // 获取一行输入的数字数组，按空格分割
            String[] splitStrs = scan.nextLine().split(" ");
            int[] array = new int[splitStrs.length]; // 创建与输入相同长度的数组

            // 将字符串数组转换为整数数组
            for (int i = 0; i < splitStrs.length; i++) {
                array[i] = Integer.parseInt(splitStrs[i]);
            }

            // 对数组进行排序
            Arrays.sort(array);

            int result = 0;  // 记录可以配对的数量
            int a = 0; // 指向最小值的指针
            int b = array.length - 1; // 指向最大值的指针

            // 双指针遍历数组，尝试配对
            while (b >= a) {
                // 如果 a 和 b 指向的元素可以组成一对（和不超过 maxValue）
                if (array[b] + array[a] <= maxValue) {
                    // 配对成功，两个指针分别向内移动
                    result++;
                    a++;
                    b--;
                } else {
                    // 如果无法配对，只有 b 指向的元素被选中，指针 b 向内移动
                    result++;
                    b--;
                }
            }

            // 输出最少需要配对的数量
            System.out.println(result);
        } catch (Exception e) {
            e.printStackTrace();
            System.out.println("input error");
        }
    }
}